/// Source : https://leetcode.com/problems/minimize-malware-spread/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13
/// Updated: 2019-09-23

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// DFS
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    int n;
    set<int> init_set;
    vector<bool> visited;
    vector<int> cc_sz;
    vector<int> cc_mal_num;

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

        for(int e: initial)
            init_set.insert(e);

        n = graph.size();
        visited.resize(n, false);

        int best = 0, res = -1, ccid = 0;
        for(int v: init_set)
            if(!visited[v]){
                cc_sz.push_back(0), cc_mal_num.push_back(0);
                cc_sz[ccid] = dfs(graph, v, ccid);
                if(cc_mal_num[ccid] == 1 && cc_sz[ccid] > best){
                    best = cc_sz[ccid];
                    res = v;
                }
                ccid ++;
            }
        return res == -1 ? *init_set.begin() : res;
    }

private:
    int dfs(const vector<vector<int>>& g, int v, int ccid){

        visited[v] = true;
        if(init_set.count(v)) cc_mal_num[ccid] ++;

        int res = 1;
        for(int next = 0; next < n; next ++)
            if(g[v][next] && !visited[next])
                res += dfs(g, next, ccid);
        return res;
    }
};


int main() {

    return 0;
}